1. Field of the Invention
The present invention relates to a method and apparatus for updating and storing information in a multi-cast system and, more particularly, to using a redundant path tree to minimize the number of messages that need to be sent to update users with changes to the system.
2. Description of the Related Art
One-way communication has always served a fundamental role in society. One-way communication allows one party to send messages or information to one or more receiving parties. An example of one-way communication is subscription television service, wherein a broadcaster sends its content to many customers.
Subscription television typically is a fee-based service. Therefore, a subscription television system operator wants to ensure that only paying customers receive its signal. A broadcaster could effect a secure system wherein only paying customers can use the service by maintaining its own network and physically adding or removing user connections, but such a system would be unduly burdensome and impractical to implement. A popular alternative is the use of encryption as a means for providing secure transmissions. Using encryption, a broadcaster can use its own equipment or a public network to send information. Any person with access to the network would be able to receive the encrypted signal, but would require a key to decipher the encrypted signal. The broadcaster provides keys to only the authorized users. Although an unintended recipient may receive the signal, the signal typically would be useless without the appropriate key.
Encrypting signals creates additional challenges for the broadcaster. The broadcaster needs a way to manage, update, or change keys every time there is a change to the intended group of recipients, e.g. whenever customers are added or deleted. Otherwise, an unauthorized recipient could still decrypt the signal. One solution would be for the broadcaster to send new keys to each authorized customer each time the group of authorized recipients is altered. This solution would require the broadcaster to send a unique message including new keys to each customer. For a system of n users, this would require the broadcaster to send n messages to update the system. Unauthorized users would not receive new keys and thus would not be able to decrypt signals. This system may be practical where there is a relatively small number of authorized users. However, as the list of authorized users grows, it can become very burdensome to send a new key to each authorized user every time the system needs to be updated.
To solve this problem, many broadcasters use a multi-cast system wherein a single message sent by the broadcaster is received by many users. This type of system may be helpful in reducing the number of messages that the broadcaster needs to send when the system is updated. With a conventional multi-cast system, it is possible to implement a method such as linear key hierarchy. As shown in FIG. 1, this method is based on a balanced binary tree 100. A balanced tree is a tree wherein each node has the same number of children. A balanced binary tree is a tree wherein each node has exactly two children. Root 110 of tree 100 represents the server (broadcaster), and each leaf 160–167 represents a user (customer). An authorized user would hold the keys associated with each node on the path from the root to that user. To change a key for a select group of users, the server would select a set of subtrees of the main tree that contain only those users. As shown in FIG. 2, the nodes of the tree that are on the paths from the root to the select group of users are referred to as the common ancestor tree nodes for those users.
When the broadcaster no longer wants a certain user to be able to decrypt the signal, the server must replace each key that the user held. Users who no longer are authorized recipients are referred to as compromises. New keys must be delivered to each of the authorized users in the system. When the server wants to exclude one user, the number of messages that must be sent to deliver the new keys is on the order of d, where d is the depth of the tree. In addition, some authorized users might not receive the initial update signal, so additional messages must be sent to ensure that the authorized users are properly updated and not erroneously treated as compromises. This is known as the late entry problem. As the number of updates increases, so does the number of late entries. If k updates are needed for a tree of depth d, approximately d*k update messages are sent.
Even though a multi-cast system greatly reduces the number of messages needed when compared with a uni-cast system, reducing the number of messages from n to log(n) (where n equals the number of users), it can still be very burdensome. Not only are some one-way communications systems very complex, they also may need to be rapidly changed and updated.
A large communication system may not be able to update its keys fast enough to provide adequate service to its customers while stopping unauthorized recipients from using proprietary information. The number of messages needed can grow exponentially with the number of users. Even though methods such as linear key hierarchy and others known in the art are an improvement over uni-cast systems, there is a need to further reduce the number of messages that must be sent when updating a system.
There are methods known in the art for reducing the number of messages that a server sends to update its network. Many of these other methods may specialize in certain types of services or networks of certain sizes. In other words, a particular method may only work well for a certain number of users or a network configured in a certain way. Even with all of these other methods, there still exists a need for a more efficient and practical method that can further reduce the number of messages sent and minimize the cost of dealing with late entries. Additionally, it would be desirable for any new method to work uniformly well, regardless of the size or type of network used.